// https://www.lintcode.com/problem/subarray-sum-closest/

public class Solution {
    /*
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    public int[] subarraySumClosest(int[] nums) {
        // write your code here
        // 序列a[i + 1]到a[j]的和等于a[0]到a[j]的和减去a[0]到a[i]的和
        int[][] sums = new int[nums.length][2];
        int tmp = 0;
        for (int i = 0; i < nums.length; ++i) {
            tmp += nums[i];
            sums[i][0] = tmp;
            sums[i][1] = i;
        }
        Arrays.sort(sums, new Comparator<int[]>() {
            @Override
            public int compare(int[] v1, int[] v2) {
                if (v1[0] == v2[0])
                    return v1[1] - v2[1];
                return v1[0] - v2[0];
            }
        });
        int[] ret = new int[2];
        int diff = Math.abs(sums[0][0]); // Python版本这里有问题需要修复
        ret[0] = 0;
        ret[1] = sums[0][1];
        for (int i = 1; i < nums.length; ++i) {
            if (Math.abs(sums[i][0] - sums[i - 1][0]) < diff) {
                diff = Math.abs(sums[i][0] - sums[i - 1][0]);
                ret[0] = Math.min(sums[i][1], sums[i - 1][1]) + 1;
                ret[1] = Math.max(sums[i][1], sums[i - 1][1]);
            }
        }
        return ret;
    }
}